package 贪心;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import org.junit.Test;

/**
 * 问题描述：
 * 给你一个字段串 数组： String [] str ，返回 str 数组 中 字符串  拼接  之后 ，返回字典序最小的  拼接之后的字符串。
 * 
 * solution：
 * 可贪 可暴：
 * 可以 暴力递归的 大部分 可以 （用dp 解决）
 */

public class Zuo字符串数组最小字典序拼接 {
	/**
	 * 暴力解法（递归）
	 */
	
	/**
	 * 返回的结果 可以直接是 
	 * TreeSet 相当于排序直接就做好了
	 * 也可以 直接 自己手动排序
	 * @return
	 */
	public static List<String> solution(String []strs){
		List<String> ans = new ArrayList<>();
		if(strs == null)
			return ans;
		int len = strs.length;
		StringBuilder path = new StringBuilder();
		boolean used[] = new boolean [len];
		process(0,len,path,ans,used,strs);
		Collections.sort(ans);
		return ans;
	}

	private static void process(int index, int len, StringBuilder path, List<String> ans,boolean used[],String []strs) {
		if(index == len) {
			ans.add(path.toString());
			// return 不return 都可以 其实效率没有 什么特别大的 影响
			return ;
		}
		for(int i = 0 ;i < len ;i++) {
			if(used[i])
				continue;
			used[i] = true;
			path.append(strs[i]);
			process(index + 1,len,path,ans,used,strs);
			used[i] = false;
			/**
			 * 这删除有点难受
			 */
			int lenStr = strs[i].length();
			int lenPath = path.length();
			//下面的 这个 start 和 end 写的是正确的 
			path.delete(lenPath - lenStr,lenPath);
		}
		
	}
	
	/**
	 * （回溯）二叉树
	 * 这种全排列的问题 就不适合 
	 * 用二叉树 （回溯） 来写 （不好写）
	 * 左成云 好像写过这种 （不过coding 还是做了一些 改变）
	 */
	public static void processBinaryTree(int index,int len,StringBuilder path,List<String> ans,boolean used[],String []strs) {
	}

	
	/**
	 * 贪心的方案（大量会用到 排序 和 堆 PriorityQueue 这种数据结构）
	 * 正确的 **贪法** 
	 * x + y <= y + x 则 x 在y 之前进行拼接 
	 * 按照上面这种排序 规则  就可以
	 */
	public static String [] greedy(String [] strs) {
		// Nlg(N) 一个复杂度
		Arrays.sort(strs,(x,y)->(x + y).compareTo(y + x));
		return strs;
	}
	
	
	
	@Test
	public void testRight() {
		String strs[] = {"ba","b","cdb","baac"};
		System.out.println(solution(strs).get(0));
		System.out.println(Arrays.toString(greedy(strs)));
	}
	
	
	
	public static void main(String []args) {
		
		StringBuilder str = new StringBuilder("docker");
		int len = str.length();
		str = str.delete(len - 3, len);
		
		System.out.println(str);
	}
	

}
